package lc_剑指_Offer_II_054_所有大于等于节点的值之和;

import java.util.Arrays;

import algorithm.helper.IConverter;
import algorithm.helper.impl.Converter;
import algorithm.helper.tree.TreeNode;

public class Solution {

	int total;
	int sum;

	public TreeNode convertBST(TreeNode root) {
		f(root);
		c(root);
		return root;
	}

	private void c(TreeNode root) {
		if (root == null) {
			return;
		}
		c(root.left);
		int val = root.val;
		root.val = total - sum;
		sum += val;
		c(root.right);

	}

	private void f(TreeNode root) {
		if (root == null) {
			return;
		}
		total += root.val;
		f(root.left);
		f(root.right);
	}

	public static void main(String[] args) {
		IConverter converter = new Converter();
		TreeNode root = converter.toTreeNode("[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]");
		Solution so = new Solution();
		TreeNode ans = so.convertBST(root);
		System.out.println(Arrays.equals(converter.toStringArray(ans),
				converter.toStringArray("[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]")));
	}

}